/*
 * TMap Designer - A Thematic Map design software
 * Copyright (C) 2006 World Health Organization
 * http://www.who.int
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 */
package who.tmap.toolkit.shape.impl;

import java.awt.geom.GeneralPath;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

import org.apache.log4j.Logger;

import who.tmap.toolkit.shape.PolygonShape;

/**
 * TMap project
 * WHO 2004-2005 
 * 
 * @author stl
 */
public class PolygonShapeImplMergeHelper extends BasePolygonShapeHelper {

    private static Logger logger = Logger.getLogger(PolygonShapeImplMergeHelper.class);    
    
    // merge states
    private static final int DRAW_MASTER_UNTIL_FIRST_OR_LAST_COMMON_POINT =0;
    private static final int DRAW_MERGED_STARTING_AT_FIRST_OR_LAST_COMMON_POINTS =1;
    private static final int FINISH_DRAWING_MASTER =2;	     
    private static final int DONE =3;       
    
    private PolygonShape polygon;
    private PolygonShape polygonToMerge; 
        
    @SuppressWarnings("unchecked")
	private List commonPoints;
	// Stores first and last common points as Point2D
	@SuppressWarnings("unchecked")
	private List flCommonPoints;  
    
	// Stores the polygon common points path
	// from the 1st to the last point including non common points!	
	@SuppressWarnings("unchecked")
	private List polygonCommonPointsPath;
	// Stores the merged polygon common points path
	// from the 1st to the last point including non common points!
	@SuppressWarnings("unchecked")
	private List mergedPolygonCommonPointsPath;	
	
	private int state =-1;
	private GeneralPath newPath =null;	
    
    public PolygonShapeImplMergeHelper( PolygonShape polygon, PolygonShape polygonToMerge ) {
        this.polygon =polygon;
        this.polygonToMerge =polygonToMerge;
    }
    
    /**
     * Iterate a polygon until its first not common point with another polygon
     * @param polygon
     * @param polygonToMerge
     * @return
     */
    @SuppressWarnings("unchecked")
	private CircularListIterator iterateUntilFirstNotCommonPoint( List polygon, List polygonToMerge ) {
        CircularListIterator clit =new CircularListIterator( (ArrayList)polygon );
        
        while( !clit.hasTraversedAllElements() ) {
            PolygonShapePoint psp =(PolygonShapePoint)clit.iterate();
            
            if ( psp.originalType != PathIterator.SEG_CLOSE &&
                 findPoint( polygonToMerge, 
                        	new Point2D.Float( psp.x, psp.y ) ) == null ) {
                clit.resetNbSteps();
                return clit;
                
            }
        }
         
        return null;
    }
    
	/**
	 * Find the first and the last common points with another polygon
	 * @return an 2 indexes array containing the first and the last common points
	 */
	@SuppressWarnings("unchecked")
	private void processFirstAndLastCommonPoints() {
	    flCommonPoints =new ArrayList();
	    
	    if ( commonPoints.size() > 0 ) {
	        flCommonPoints.add( commonPoints.get(0) );
	        logger.debug( "flCP0=" + commonPoints.get(0) );
	    } 
	    
	    if ( commonPoints.size() > 1 ) {
	        flCommonPoints.add( commonPoints.get( commonPoints.size() - 1 ) );
	        logger.debug( "flCP1=" + commonPoints.get( commonPoints.size() - 1 ) );	        
	    } 
	}     
	
    /**
     * Check if two lists have at least one common element
     * @param list1
     * @param list2
     * @return true if list1 and list2 have at least one common point, false otherwise
     */
    @SuppressWarnings("unchecked")
	private boolean shareAnyPoints( List list1, List list2 ) {
       
        for( int ct1 =0; ct1 < list1.size(); ct1++ ) {
            Object p1 =list1.get( ct1 ); 

            for( int ct2 =0; ct2 < list2.size(); ct2++ ) {
                Object p2 =list2.get( ct2 );
                
                if ( p1.equals( p2 ) ) {
                    return true;
                }
            }
        }
        
        return false;
    }	
    
    private int[] lookForContiguousPolygons( List<PolygonShapePoint> polygons ) {
        ListIterator<PolygonShapePoint> lit1 =polygons.listIterator();
        while( lit1.hasNext() ) {
            PolygonShapePoint psp1 =(PolygonShapePoint)lit1.next();
            
            ListIterator<PolygonShapePoint> lit2 =polygons.listIterator();
            while( lit2.hasNext() ) {
                PolygonShapePoint psp2 =(PolygonShapePoint)lit2.next();
                
                if ( psp1.polygonId != psp2.polygonId 
                        && psp1.x == psp2.x && psp1.y == psp2.y ) {
			        return new int[] { psp1.polygonId, psp2.polygonId };                    
                }
            }
        }
        
        return null;
    }
    
    /**
     * Process the common points for the two polygons
     */
    @SuppressWarnings("unchecked")
	private void processCommonPoints( List polygonPts, List polygonToMergePts ) {
		float xFirst, yFirst, prevMoveToX =-1, prevMoveToY =-1;
		int typeFirst, prevType =-1;
		
		commonPoints =new ArrayList();
		
        CircularListIterator clit =iterateUntilFirstNotCommonPoint( polygonPts, polygonToMergePts );
        PolygonShapePoint psp =(PolygonShapePoint)clit.getCurrentElement();
		typeFirst =psp.type;
		xFirst =psp.x;
		yFirst =psp.y;        
        
        while( !clit.hasTraversedAllElements() ) {
            psp =(PolygonShapePoint)clit.iterate();
        
			if ( prevType != PathIterator.SEG_CLOSE &&
			        findPoint( polygonToMergePts, 
                    		   new Point2D.Float( psp.x, psp.y ) ) != null ) {
			    Point2D pt;
			    
			    if ( psp.type != PathIterator.SEG_CLOSE ) {
			        pt =new Point2D.Float( psp.x, psp.y );
			    } else {
			        pt =new Point2D.Float( prevMoveToX, prevMoveToY );
			    }
			    
			    if ( !commonPoints.contains( pt ) ) {
			        commonPoints.add( pt );
			    }
			}
			
			prevType =psp.type;
			
			if ( psp.type == PathIterator.SEG_MOVETO ) {
			    prevMoveToX =psp.x;
			    prevMoveToY =psp.y;
			}

		}
        
        processFirstAndLastCommonPoints();
        
        // remove first and last points from the common coordinates
        if ( flCommonPoints != null ) {
            commonPoints.removeAll( flCommonPoints );
        }	         
		    
    }
    
	/**
	 * Compute common points paths for both polygons
	 * It is useful for common boundaries including another polygon ("island")
	 */    
    @SuppressWarnings("unchecked")
	private void processCommonPointsPaths( List polygonPts, List polygonToMergePts ) {
	    polygonCommonPointsPath =computeCommonPointsPath( polygonPts, CircularListIterator.FORWARD );
	    mergedPolygonCommonPointsPath =computeCommonPointsPath( polygonToMergePts, CircularListIterator.FORWARD );
	}
	
	@SuppressWarnings("unchecked")
	private List computeCommonPointsPath( List<PolygonShapePoint> aPolygon, int direction ) {
	    int state =0;
	    Point2D firstPt =null;
	    List<Point2D> cpp =new ArrayList<Point2D>();
    
        CircularListIterator clit =iterateUntilFirstNotCommonPathPoint( aPolygon, direction );
        
        while( !clit.hasTraversedAllElements() ) {
            PolygonShapePoint psp =(PolygonShapePoint)clit.iterate();
            
	        Point2D pt =new Point2D.Float( psp.x, psp.y );
	        if ( flCommonPoints.contains( pt ) ) {
	            // found one of the fl common points
	            if ( state == 0 ) {
	                state =1;
	                firstPt =new Point2D.Float( (float)pt.getX(), (float)pt.getY() );
	            // found second of the fl common points
	            } else if ( state == 1 && !pt.equals( firstPt ) ) {
	                state =2;
	                break;
	            } 
	        // common point path
	        } else if ( state == 1 ) {
	            cpp.add( pt );	            
	        }	            
        }
        
	    if ( cpp != null && !shareAnyPoints( commonPoints, cpp ) ) {
	        cpp =computeCommonPointsPath( aPolygon, CircularListIterator.BACKWARD );
	    }
	    
	    return cpp;
	}
	
	@SuppressWarnings("unchecked")
	private CircularListIterator iterateUntilFirstNotCommonPathPoint( List<PolygonShapePoint> polygon, int direction ) {
	    CircularListIterator clit =new CircularListIterator( (ArrayList)polygon );
	    clit.setDirection( direction );
	    
	    while( !clit.hasTraversedAllElements() ) {
            PolygonShapePoint psp =(PolygonShapePoint)clit.iterate();
	           
	        Point2D pt =new Point2D.Float( psp.x, psp.y );
	        if ( !commonPoints.contains( pt ) && !flCommonPoints.contains( pt ) 
	            
	            //CircularListIterator clitClone =(CircularListIterator)clit.clone();
	            //clitClone.iterateUntil( psp );
	            &&  !isPartOfTheBoundary( polygon, psp ) ) {
	                clit.resetNbSteps();
	                return clit;
	            
	        }
	    }
	    
	    return null;
	}
	
    @SuppressWarnings("unchecked")
	private boolean isPartOfTheBoundary( List aPolygon, PolygonShapePoint startingPsp ) {
        PolygonShapePoint pp =null;
        int commonPointCt =0;
        int flCommonPointCt =0;
        
        CircularListIterator clit =new CircularListIterator( (ArrayList)aPolygon );
        clit.iterateUntil( startingPsp );        
        while( !clit.hasTraversedAllElements() ) {
            pp =(PolygonShapePoint)clit.iterate();
	        
	        Point2D pt =new Point2D.Float( pp.x, pp.y );
	        
	        if ( commonPoints.contains( pt ) ) {
	            commonPointCt++;	            
	            
	            // Found a common point without any flcommon point before
	            // so it's part of the common points
	            if ( flCommonPointCt == 0 ) {
	                return true;
	            }
        
	        } else if ( flCommonPoints.contains( pt ) ) {
	            flCommonPointCt++;	            
	            
	            // Found a fl common point after having found common points
	            // so it's part of the common points
	            if ( flCommonPointCt == 1 && commonPointCt > 0 ) {
	                return true;
	            }
	            
	            // Found 2 fl common points and found all the common points
	            // so it's not part of the common points
	            if ( flCommonPointCt == 2 && commonPointCt == commonPoints.size() ) {
	                return false;
	            }
	            
	        }
	        
	        
	        	    
        }
        
        return false;
    }	
    
    @SuppressWarnings("unchecked")
	private void addNewPoint( List newPol, PolygonShapePoint psp ) {
        PolygonShapePoint psp2 =(PolygonShapePoint)psp.clone();
        
        // First point has to be a move to (force move to)
        if ( newPol.size() == 0 ) {
            if ( psp2.type != PathIterator.SEG_MOVETO ) { 
                //PolygonShapePoint psp2 =(PolygonShapePoint)psp.clone();
                psp2.type =PathIterator.SEG_MOVETO;
                
                //newPol.add( psp2 );
            } /*else {
                newPol.add( psp2 );
            }*/
        // after that, cant be a move to (force line to)
        } else if ( psp.type == PathIterator.SEG_MOVETO ) {
            //PolygonShapePoint psp2 =(PolygonShapePoint)psp.clone();
            psp2.type =PathIterator.SEG_LINETO;
            
            //newPol.add( psp2 );            
        } /*else {
            newPol.add( psp2 );
        }*/
        
        newPol.add( psp2 );
        
    }
    
    @SuppressWarnings("unchecked")
	private CircularListIterator drawMasterUntilFirstOrLastCommonPoint( List polygonPts, List polygonToMergePts, CircularListIterator cli, List newPol ) {
        CircularListIterator polToMergeCli =null;
        PolygonShapePoint psp =(PolygonShapePoint)cli.getCurrentElement();
	    
		int type =psp.type;
		float x =psp.x;
		float y =psp.y;
		Point2D pt =new Point2D.Float( x, y );
		
		// first point(s) of the master polygon is inside the common points
		// we continue (do nothing) until finding the first or the last common points
		if ( polygonCommonPointsPath.contains( pt ) ) {

		// we just hit the first or the last common points    
		} else if ( flCommonPoints.contains( pt ) ) {
		    addNewPoint( newPol, psp );
		    
		    int direction =CircularListIterator.FORWARD;

		    // look for this point (first or last) in the merged polygon 		    
		    polToMergeCli =iterateUntilPoint( (ArrayList)polygonToMergePts, pt, direction );
		    if ( polToMergeCli != null ) {
		        PolygonShapePoint mergePsp =(PolygonShapePoint)polToMergeCli.iterate();

		        // if the point after pt (the first or last common point) is part of the common points
	            // then we need to reverse the drawing direction of the polygon to merge 
	            if ( mergedPolygonCommonPointsPath.contains( new Point2D.Float( mergePsp.x, mergePsp.y ) ) ) {
	                logger.debug( "Reversing direction" );
	                direction =polToMergeCli.reverseDirection();
	                
				    polToMergeCli =iterateUntilPoint( (ArrayList)polygonToMergePts, pt, direction );
				    mergePsp =(PolygonShapePoint)polToMergeCli.iterate();	                
	            }
	     
		    }
		    		    
		    state =DRAW_MERGED_STARTING_AT_FIRST_OR_LAST_COMMON_POINTS;
		} else {
		    
		    addNewPoint( newPol, psp );
		}
		
		cli.iterate();
		
		return polToMergeCli;
    }
    
    @SuppressWarnings("unchecked")
	private void drawMergedStartingAtFirstOrLastCommonPoints( CircularListIterator polToMergeCli, List newPol ) {
        PolygonShapePoint psp =(PolygonShapePoint)polToMergeCli.getCurrentElement();
        		
		Point2D pt =new Point2D.Float( psp.x, psp.y );
	    
		// inside the common points
		// we continue until finding the "other" common points					
		if ( mergedPolygonCommonPointsPath.contains( pt ) ) {
		    
		// we just hit the first or the last common points    
		} else if ( flCommonPoints.contains( pt ) ) {
		   addNewPoint( newPol, psp );
		    
		    state =FINISH_DRAWING_MASTER;
		} else {
		    addNewPoint( newPol, psp );
		}

		polToMergeCli.iterate();
    }
    
    @SuppressWarnings("unchecked")
	private void finishDrawingMaster( CircularListIterator polCli, List newPol ) {
        PolygonShapePoint psp =(PolygonShapePoint)polCli.getCurrentElement();
	    
		Point2D pt =new Point2D.Float( psp.x, psp.y );			    
		
		/*if ( polygonPtCt == firstNotCommonPointIdx 
		        || ( firstNotCommonPointIdx == 0 && polygonPtCt == polygon.size() -1)) {*/
		if ( polCli.hasTraversedAllElements() ) {
		    /*if ( newPath.getCurrentPoint() != null ) {
		        newPath.closePath();
		    }*/
		    addNewPoint( newPol, psp );
		    state =DONE;
    	
		// we just hit the first or the last common points    
		} else if ( polygonCommonPointsPath.contains( pt ) ) {
		} else if ( flCommonPoints.contains( pt ) ) {		    
		} else {
		    addNewPoint( newPol, psp );
		}				    
	    
		polCli.iterate();	        
        
    }
    
    @SuppressWarnings("unchecked")
	private void mergeUpdatedPolygon( List<PolygonShapePoint> newPol, List<PolygonShapePoint> polygons, int[] contiguousPolygons ) {
		float prevX =Float.MIN_VALUE, prevY =Float.MAX_VALUE;
		
		// Assign the "master" polygon id to every point of the new polygon
		ListIterator lit =newPol.listIterator();
		while( lit.hasNext() ) {
		    PolygonShapePoint psp =(PolygonShapePoint)lit.next();
		    
		    // Remove contiguous identical points
		    if ( psp.x == prevX && psp.y == prevY ) {
		        lit.remove();
		    }
		    
		    prevX =psp.x;
		    prevY =psp.y;
		    
		    psp.polygonId =contiguousPolygons[0];
		}
		
		removePointsForPolygonId( contiguousPolygons[1], (ArrayList)polygons );
        removePointsForPolygonId( contiguousPolygons[0], (ArrayList)polygons );
        polygons.addAll( newPol );	        
    }
    
    public GeneralPath merge() { 
        int polygonsMergedCt =0;
        
        closedPolygonCt =0;

        List<PolygonShapePoint> polygonPts =generalPathToArray( polygon.getGeneralPath() );
        logger.debug( polygonToMerge );        
        List<PolygonShapePoint> polygonToMergePts =generalPathToArray( polygonToMerge.getGeneralPath() );
        logger.debug( "nb polygons=" + closedPolygonCt );
        
        List<PolygonShapePoint> polygons =new ArrayList<PolygonShapePoint>();
        polygons.addAll( polygonPts );
        polygons.addAll( polygonToMergePts );
        
        int[] contiguousPolygons =null;
        
        do {
            contiguousPolygons =lookForContiguousPolygons( polygons );
        
            if ( contiguousPolygons != null ) {
                
                polygonsMergedCt++;
                logger.debug( "merge iteration " + polygonsMergedCt + " ids=( " + contiguousPolygons[0] + ", " + contiguousPolygons[1] + ")" );
                
                List<PolygonShapePoint> polPts =extractPointsForPolygonIdOnly( contiguousPolygons[0], 
                        									polygons );
                
                List<PolygonShapePoint> polToMergePts =extractPointsForPolygonIdOnly( contiguousPolygons[1], 
					 	  										   polygons );
             
                processCommonPoints( polPts, polToMergePts );
                logger.debug( "common points size=" + commonPoints.size() );		        
		        
		        processCommonPointsPaths( polPts, polToMergePts );
		        logger.debug( "polygon common points paths size=" + polygonCommonPointsPath.size() + "\npolygon to merge common points paths size=" + mergedPolygonCommonPointsPath.size() );
		        
		        //logger.debug( "polygons=" + polygons );
		        
		        List<PolygonShapePoint> newPol =new ArrayList<PolygonShapePoint>();
		        
		        CircularListIterator polToMergeCli =null;
		        CircularListIterator polCli =iterateUntilFirstNotCommonPathPoint( polPts, CircularListIterator.FORWARD ); 		        
				
		        state =DRAW_MASTER_UNTIL_FIRST_OR_LAST_COMMON_POINT;
		        
				while( state != DONE ) {
					
				    switch( state ) {
				    	case DRAW_MASTER_UNTIL_FIRST_OR_LAST_COMMON_POINT:
				    	    polToMergeCli =drawMasterUntilFirstOrLastCommonPoint( polPts, polToMergePts, polCli, newPol );
				    	    break;
					    
						case DRAW_MERGED_STARTING_AT_FIRST_OR_LAST_COMMON_POINTS:
						    drawMergedStartingAtFirstOrLastCommonPoints( polToMergeCli, newPol );
						    break;
					    
						case FINISH_DRAWING_MASTER:
						    finishDrawingMaster( polCli, newPol );
						    break;
					}
		
				} // while
				
			    mergeUpdatedPolygon( newPol, polygons, contiguousPolygons );
	
				
            } // if  
            
            
        } while ( contiguousPolygons != null );
        
        GeneralPath newPath =null;
        
        if ( polygonsMergedCt != 0 ) {
            logger.debug( "merged polygon contains " + polygons.size() + " points." );
            newPath =arrayToGeneralPath( polygons );
        }         
        
        return newPath;
    }

}
